package com.zjsru.oneDay202211;

/**
 * @Author: CookLee
 * @Date: 2022/11/24
 * 区间子数组个数:给你一个整数数组 nums 和两个整数：left 及 right 。找出 nums 中连续、非空且其中最大元素在范围 [left, right] 内的子数组，并返回满足条件的子数组的个数。
 *
 * 输入：nums = [2,1,4,3], left = 2, right = 3
 * 输出：3
 * 解释：满足条件的三个子数组：[2], [2, 1], [3] (连续)
 *
 * 输入：nums = [2,9,2,5,6], left = 2, right = 8
 * 输出：7
 *
 */
public class NumSubarrayBoundedMax {
    
    /**
     * 模拟
     */
    public int numSubarrayBoundedMax(int[] nums, int left, int right) {
        int ans = 0;
        int len = nums.length;
        //变量 j 和 k 分别记录最近一次满足nums[i] 范围落在 [left,right] 之间」以及「nums[i]数值大于 right的下标位置。
        int k = -1, j = -1;
        for (int i = 0; i < len; i++) {
            //nums[i] 大于 right，nums[i] 作为右端点，必不可能贡献合法子数组。更新 k；
            if (nums[i] > right) {
                k = i;
            } else {
                //nums[i] 小于 left
                if (nums[i] < left) {
                    //说明范围在 (k,j) 均能作为子数组的左端点，累加方案数 j−k
                    if (j > k) {
                        ans += j - k;
                    }
                } else {
                    //nums[i] 落在范围 [left,right]，此时 nums[i] 想作为右端点的话，
                    // 只需要找到左边第一个数值大于 right 的数值即可（即变量 k），累加方案数 i−k。更新 j。
                    ans += i - k;
                    j = i;
                }
            }
        }
        return ans;
    }
    
    public static void main(String[] args) {
        NumSubarrayBoundedMax numSubarrayBoundedMax = new NumSubarrayBoundedMax();
        int[] nums = new int[] {2, 1, 4, 3};
        int left = 2;
        int right = 3;
        System.out.println(numSubarrayBoundedMax.numSubarrayBoundedMax(nums, left, right));
    }
}
